%\input{template}
\documentclass[11pt]{article}
%\documentclass{sig-alternate}
\usepackage{algorithm}
\usepackage{algorithmic}

\usepackage{subfigure}
\usepackage{epsfig,amsthm,amsmath,color, amsfonts}
\usepackage{epsfig,color}
\newcommand{\xxx}[1]{\textcolor{red}{#1}}
%\usepackage{fullpage}
\usepackage{framed}
%\usepackage{epsf}
%\usepackage{hyperref}

%\setlength{\textheight}{9.4in} \setlength{\textwidth}{6.55in}
\setlength{\textheight}{9.2in} \setlength{\textwidth}{6.55in}
%\setlength{\topmargin}{0in}

\voffset=-0.9in
\hoffset=-0.8in

\newtheorem{theorem}{Theorem}[section]
%\newtheorem{definition}[theorem]{Definition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
%\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
\theoremstyle{definition}\newtheorem{example}[theorem]{Example}
\theoremstyle{definition}\newtheorem{definition}[theorem]{Definition}
\theoremstyle{observation}\newtheorem{observation}[theorem]{Observation}

\newcommand{\comment}[1]{}
\newcommand{\QED}{\mbox{}\hfill \rule{3pt}{8pt}\vspace{10pt}\par}
%\newcommand{\eqref}[1]{(\ref{#1})}
\newcommand{\theoremref}[1]{(\ref{#1})}
\newenvironment{proof1}{\noindent \mbox{}{\bf Proof:}}{\QED}
%\newenvironment{observation}{\mbox{}\\[-10pt]{\sc Observation.} }%
%{\mbox{}\\[5pt]}

\def\m{{\rm min}}
%\def\m{\bar{m}}
\def\eps{{\epsilon}}
\def\half{{1\over 2}}
\def\third{{1\over 3}}
\def\quarter{{1\over 4}}
\def\polylog{\operatorname{polylog}}
\newcommand{\ignore}[1]{}
\newcommand{\eat}[1]{}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}

\newcommand{\algorithmsize}[0]{}

%---------------------
%  SPACE SAVERS
%---------------------

\usepackage{times}
\usepackage[small,compact]{titlesec}
\usepackage[small,it]{caption}

\newcommand{\squishlist}{
 \begin{list}{$\bullet$}
  { \setlength{\itemsep}{0pt}
     \setlength{\parsep}{3pt}
     \setlength{\topsep}{3pt}
     \setlength{\partopsep}{0pt}
     \setlength{\leftmargin}{1.5em}
     \setlength{\labelwidth}{1em}
     \setlength{\labelsep}{0.5em} } }
\newcommand{\squishend}{
  \end{list}  }

%
%\newcommand{\squishlist}{
% \begin{enumerate}}
%\newcommand{\squishend}{
%  \end{enumerate}  }


%---------------------------------
% FOR MOVING PROOFS TO APPENDIX
%\usepackage{answers}
%%\usepackage[nosolutionfiles]{answers}
%\Newassociation{movedProof}{MovedProof}{movedProofs}
%\renewenvironment{MovedProof}[1]{\begin{proof}}{\end{proof}}

\def\e{{\rm E}}
\def\var{{\rm Var}}
\def\ent{{\rm Ent}}
\def\eps{{\epsilon}}
\def\lam{{\lambda}}
\def\bone{{\bf 1}}


%First definitions. Use these when you want to read comments.
%\def\prasad#1{\marginpar{$\leftarrow$\fbox{P}}\footnote{$\Rightarrow$~{\sf #1 --Prasad}}}
\def\danupon#1{\marginpar{$\leftarrow$\fbox{D}}\footnote{$\Rightarrow$~{\sf #1 --Danupon}}}
%\def\gopal#1{\marginpar{$\leftarrow$\fbox{G}}\footnote{$\Rightarrow$~{\sf #1 --Gopal}}}
%\def\atish#1{\marginpar{$\leftarrow$\fbox{A}}\footnote{$\Rightarrow$~{\sf #1 --Atish}}}
%
%Second definitions. Use these to remove all comments.
\def\prasad#1{}
%\def\danupon#1{}
\def\gopal#1{}
\def\atish#1{}


\begin{document}


\title{Distributed Complexity Classes
%\footnote{Eligible for Best Student Paper Award. Students recommended for award - Atish {Das Sarma} and Danupon Nanongkai.}
}

\begin{titlepage}
%\author{Atish {Das Sarma} \thanks{Google Research, Google Inc., Mountain View, CA 94041, USA.
%\hbox{E-mail}:~{\tt dassarma@google.com}.} \and Danupon Nanongkai \thanks{College of Computing, Georgia Institute of Technology, Atlanta, GA 30332, USA. \hbox{E-mail}:~{\tt danupon@cc.gatech.edu}.}
%\footnotemark \and  Gopal Pandurangan \thanks{Division of Mathematical
%Sciences, Nanyang Technological University, Singapore 637371 and Department of Computer Science, Brown University, Providence, RI 02912.  \hbox{E-mail}:~{\tt gopalpandurangan@gmail.com}. Supported in part by NSF grant CCF-0830476.}   \and Prasad Tetali \thanks{School of Mathematics and School of Computer Science,
%Georgia Institute of Technology, Atlanta, GA 30332, USA. \hbox{E-mail}:~{\tt tetali@math.gatech.edu}. Supported in part by NSF DMS 0701023 and NSF CCR 0910584.}}

\date{}

\maketitle \thispagestyle{empty}

\vspace*{.4in}


\maketitle
\begin{abstract}
Distributed Complexity classes. 
\end{abstract}

%\noindent {\bf Keywords:} Random walks, Random sampling, Decentralized
%computation, Distributed algorithms, Random Spanning Tree, Mixing Time. \\

%\noindent {\bf Format:} Regular Presentation.

\end{titlepage}


\vspace{-0.15in}
\section{Introduction}
New classes for distributed complexity. Threshols are $O(\log n)$, $D$, $D + \sqrt{n}$, $m$ (for all information). 

All graph problems that satisfy generic property $P$, can we say they can be solved in $D + \sqrt{n}$ ? 

Compare between $NP-completeness$ where verification is easy.. here verification is hard... but no notion of "completeness".

Draw analogy. 

Conceptual paper with new insights perhaps even new results? 

\subsection{Problem Statement, Motivation, and Related Work}


\subsection{Our Results}

  \let\oldthebibliography=\thebibliography
  \let\endoldthebibliography=\endthebibliography
  \renewenvironment{thebibliography}[1]{%
    \begin{oldthebibliography}{#1}%
      \setlength{\parskip}{0ex}%
      \setlength{\itemsep}{0ex}%
  }%
  {%
    \end{oldthebibliography}%
  }
{ \small
\bibliographystyle{abbrv}
\bibliography{Distributed-RW}
}

\end{document}
